package algorithm.weightgraph;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

public class PrimMST<Weight extends Number&Comparable> {


    //是否已访问过
    private boolean[] visited;
    //已在堆中点的边
    private Edge<Weight>[] edgeTo;

    private Graph<Weight> graph;

    private MinIndexHeap<Edge<Weight>> minHeap;

    private List<Edge<Weight>> mst;

    private Number mstWeight;


    public PrimMST(Graph graph){
        this.graph = graph;
        this.visited = new boolean[graph.getPointNums()];
        this.edgeTo = new Edge[graph.getEdgeNums()];
        this.minHeap = new MinIndexHeap<>(graph.getEdgeNums());
        mst = new LinkedList<>();
        mstWeight = Double.valueOf(0);

        visit(0);

        while (!minHeap.isEmpty()){
            Edge<Weight> edge = minHeap.exportMin();
            mst.add(edge);
            if (!visited[edge.other(0)]){
                visit(edge.other(0));
            }
        }
    }


    private void visit(int p){
        if (visited[p]){
            return;
        }
        visited[p]=true;

        Iterator<Edge<Weight>> iterator = graph.getIterator(p);
        while (iterator.hasNext()){
            Edge<Weight> e = iterator.next();
            //没有访问过才能加入堆
            if (!visited[e.other(p)]){
                //已经加入堆，但是还没被访问
                Edge<Weight> edge = edgeTo[e.other(p)];
                if (edge !=null){
                    if (e.getWeight().compareTo(edge.getWeight())<0){
                        minHeap.change(e.other(p),e);
                    }
                }else{
                    //没有加入堆
                    minHeap.insert(e.other(p),e);
                }
            }
        }
    }
}
